﻿#pragma once
#include <iostream>
#include <vector>
#include <map>

using namespace std;

namespace Matrix
{
	// V 代表顶点  W 代表权重  默认是无向图
	template<class V,class W,W MAX_W = INT_MAX,bool Direction = false>
	class Graph
	{
	public:
		// "0123"  长度 4
		Graph(const V* vertex, int n)
		{
			_vertex.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertex.push_back(vertex[i]);//添加顶点
				_vIndexMap[vertex[i]] = i;//映射关系
			}

			_matrix.resize(n);
			for (auto& e : _matrix)
			{
				e.resize(n, INT_MAX);
			}
		}

		// 获取顶点的下标
		size_t GetvIndexMap(const V& v)
		{
			//检查下标是否合法
			auto it = _vIndexMap.find(v);
			if (it != _vIndexMap.end())
			{
				//找到了
				return it->second;
			}
			else
			{
				//非法的顶点
				throw invalid_argument("你传递了一个无效的顶点!");
				return -1;
			}
		}

		void _AddEdge(size_t src, size_t dest, const W& w)
		{
			_matrix[src][dest] = w;

			//判断是否是无向图
			if (Direction == false)
			{
				_matrix[dest][src] = w;
			}
		}

		//添加边的关系  起点边  终点边  权重
		void AddEdge(const V& src, const V& dest, const W& w)
		{
			//找到边的下标
			size_t srcIndex = GetvIndexMap(src);
			size_t destIndex = GetvIndexMap(dest);

			_AddEdge(srcIndex, destIndex, w);
		}

		//打印
		void Print()
		{
			//顶点的映射关系
			for (int i = 0; i < _vertex.size(); i++)
			{
				cout << "[" << _vertex[i] << "]" << " --> " << i << endl;
			}
			cout << endl << endl;

			cout << "  ";
			for (int i = 0; i < _vertex.size(); i++)
			{
				cout << i << " ";
			}
			cout << endl;

			//打印矩阵
			for (int i = 0; i < _matrix.size(); i++)
			{
				cout << i << " ";
				for (int j = 0; j < _matrix[i].size(); j++)
				{
					
					if (_matrix[i][j] != MAX_W)
					{
						cout << _matrix[i][j] << " ";
					}
					else
					{
						if (i == j)
						{
							cout << "0" << " ";
						}
						else
						{
							cout << "*" << " ";
						}
					}
				}
				cout << endl;
			}
		}
	private:
		vector<V> _vertex;//顶点集合
		map<V, int> _vIndexMap;//顶点和下标关系的映射
		vector<vector<int>> _matrix;//存储权重的矩阵
	};

	void TestGraph()
	{
		Graph<char, int, INT_MAX, true> g("ABCD", 4);
		g.AddEdge('A', 'B', 1);
		g.AddEdge('A', 'D', 4);
		g.AddEdge('B', 'D', 2);
		g.AddEdge('B', 'C', 9);
		g.AddEdge('C', 'D', 8);
		g.AddEdge('C', 'B', 5);
		g.AddEdge('C', 'A', 3);
		g.AddEdge('D', 'C', 6);

		g.Print();
	}
}
